import sys
# Install gurobi
!{sys.executable} -m pip install -i https://pypi.gurobi.com gurobipy
!{sys.executable} -m pip install plotly geopy
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import pandas as pd
from itertools import product
import gurobipy as gp
from gurobipy import GRB, quicksum
# These are ours
import problem
import visualization
Looking in indexes: https://pypi.gurobi.com Requirement already satisfied: gurobipy in /opt/anaconda3/lib/python3.8/site-packages (9.1.1) Requirement already satisfied: plotly in /opt/anaconda3/lib/python3.8/site-packages (4.14.3) Requirement already satisfied: geopy in /opt/anaconda3/lib/python3.8/site-packages (2.1.0) Requirement already satisfied: six in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.15.0) Requirement already satisfied: retrying>=1.3.3 in /opt/anaconda3/lib/python3.8/site-packages (from plotly) (1.3.3) Requirement already satisfied: geographiclib<2,>=1.49 in /opt/anaconda3/lib/python3.8/site-packages (from geopy) (1.50)
def normalize(i, j):
assert i != j
return (i, j) if i < j else (j, i)
from model import Autonomax, Config
# Run on the first |C| cities (mostly for testing)
C = 41
# What scenario we will be utilizing
scenario = 0
# The number of cities in the core net
NC = 3
# 1 if the core net should be a cycle; 0 if it shoul be a path.
Z = 0
autonomax = Autonomax(
Config(
cities=problem.cities[:C],
distances=problem.D[:C, :C],
demand=problem.B[scenario][:C],
core_city_count=NC,
core_net_is_cycle=Z,
)
)
Academic license - for non-commercial use only - expires 2021-05-15 Using license file /Users/sjurwold/gurobi.lic
A = autonomax.model.getA()
count = lambda d: len(d) if isinstance(d, gp.tupledict) else 1
V = sum(count(v) for v in autonomax.variables.values())
C = sum(count(c) for c in autonomax.constraints.values())
print(f'V = {V}, C = {C}')
fig, ax = plt.subplots(1, figsize=(128, 128 * C/V))
ax.set_xticklabels([])
ax.set_yticklabels([])
plt.spy(A)
total = 0
print(f'\nCONSTRAINT SETS:')
for (name, constraint) in autonomax.constraints.items():
constraints_in_set = count(constraint)
print(f'{constraints_in_set:>5} | {name}')
#plt.gcf().text(0.07, 0.69 - 0.4 * (total + 0.5 * count(constraint)) / C, name, fontsize=14)
total += constraints_in_set
plt.plot([0, V], [total - 0.5, total - 0.5], color='grey')
total = 0
print(f'\nVARIABLE SETS:')
for (name, variables) in autonomax.variables.items():
variables_in_set = count(variables)
print(f'{variables_in_set:>5} | {name}')
#plt.gcf().text(0.1 + 0.8 * (total + 0.5*count(variables)) / V, 0.8, name, fontsize=14)
total += count(variables)
plt.plot([total - 0.5, total - 0.5], [0, C], color='grey')
plt.savefig('constraint-matrix.png', dpi=200)
V = 7667, C = 5292
CONSTRAINT SETS:
1 | one_control_center
41 | control_city_directly_connected
1681 | reduce_control_center_symmetry
41 | core_city_ub
1 | cycle_or_path
41 | disallow_core_tree
1 | exactly_nc_core_cities
41 | control_center_is_connected
1640 | is_connectable
82 | is_connected_timestep
41 | connected_graph
41 | conservation_of_flow
820 | force_edge_if_flow
820 | edge_cost_lb
VARIABLE SETS:
41 | is_control_center
820 | is_core_edge
41 | is_core_city
123 | is_connected_step
3362 | is_connectable_step
820 | flow
820 | abs_flow
820 | is_sub_edge
820 | edge_cost
autonomax.model.Params.timeLimit = 600.0
autonomax.model.optimize()
Changed value of parameter timeLimit to 600.0
Prev: inf Min: 0.0 Max: inf Default: inf
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 5292 rows, 7667 columns and 25297 nonzeros
Model fingerprint: 0xe4067544
Model has 820 general constraints
Variable types: 2460 continuous, 5207 integer (5207 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+05]
Objective range [1e+00, 2e+04]
Bounds range [1e+00, 1e+02]
RHS range [7e-01, 4e+01]
Presolve removed 89 rows and 1768 columns
Presolve time: 0.08s
Presolved: 5203 rows, 5899 columns, 25437 nonzeros
Variable types: 2460 continuous, 3439 integer (3439 binary)
Found heuristic solution: objective 73101.586734
Root relaxation: objective 7.420685e+02, 5480 iterations, 0.13 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 742.06853 0 157 73101.5867 742.06853 99.0% - 0s
H 0 0 73060.052676 765.73809 99.0% - 0s
0 0 1663.98150 0 239 73060.0527 1663.98150 97.7% - 0s
H 0 0 42821.401419 1663.98150 96.1% - 0s
0 0 2080.32387 0 256 42821.4014 2080.32387 95.1% - 0s
0 0 2080.32387 0 257 42821.4014 2080.32387 95.1% - 0s
0 0 2080.32387 0 256 42821.4014 2080.32387 95.1% - 0s
H 0 0 23337.551631 2207.44607 90.5% - 0s
0 0 2207.44607 0 255 23337.5516 2207.44607 90.5% - 0s
0 0 2207.44607 0 236 23337.5516 2207.44607 90.5% - 1s
H 0 0 21087.311362 2207.44607 89.5% - 1s
H 0 0 18042.532077 2207.44607 87.8% - 1s
0 2 2207.44607 0 235 18042.5321 2207.44607 87.8% - 1s
H 71 46 17882.682740 2207.44607 87.7% 293 3s
H 73 46 17785.839466 2207.44607 87.6% 290 3s
H 109 72 16420.853426 2214.98583 86.5% 235 3s
H 111 72 14753.726066 2214.98583 85.0% 233 3s
H 156 101 14699.050959 2214.98583 84.9% 210 4s
H 158 101 14657.581994 2214.98583 84.9% 212 4s
H 159 101 14646.634271 2214.98583 84.9% 211 4s
286 230 3932.61195 39 188 14646.6343 2214.98583 84.9% 150 5s
H 381 286 14636.634271 2214.98583 84.9% 134 5s
H 383 286 14634.156449 2214.98583 84.9% 133 5s
H 666 519 14592.687484 2214.98583 84.8% 104 6s
1537 1159 11700.5131 61 150 14592.6875 2214.98583 84.8% 100 10s
1545 1168 2214.98583 15 311 14592.6875 2214.98583 84.8% 108 15s
1681 1194 2742.98230 24 249 14592.6875 2742.98230 81.2% 123 20s
2386 1261 3604.98409 35 247 14592.6875 2914.17691 80.0% 127 25s
2946 1316 6571.71374 22 202 14592.6875 3217.19456 78.0% 139 30s
H 2951 1226 14092.660686 3217.19456 77.2% 140 30s
H 2958 1221 13960.022699 3217.19456 77.0% 140 30s
H 3004 1149 13872.656843 3217.19456 76.8% 139 30s
H 3156 1112 13861.477618 3590.91000 74.1% 139 31s
H 3158 1063 13847.779356 3590.91000 74.1% 140 31s
H 3159 1017 13836.577999 3590.91000 74.0% 140 31s
H 3160 971 13826.577999 3590.91000 74.0% 140 31s
3616 1055 6612.12142 34 139 13826.5780 3948.18207 71.4% 141 35s
4353 1456 5604.28252 65 190 13826.5780 4765.65113 65.5% 139 40s
5658 2167 9653.94092 125 181 13826.5780 5975.52342 56.8% 133 45s
H 5906 2245 13799.273597 6269.72177 54.6% 133 45s
H 6423 2439 13495.071643 6353.92326 52.9% 129 47s
H 6722 2605 13461.226176 6353.92326 52.8% 130 49s
6959 2721 11985.0867 107 132 13461.2262 7047.27087 47.6% 131 50s
8716 3292 8501.02757 64 305 13461.2262 8124.44530 39.6% 132 55s
11032 3859 cutoff 47 13461.2262 8984.53230 33.3% 132 60s
13243 4099 9663.25726 37 204 13461.2262 9434.93514 29.9% 131 66s
14745 4250 12247.2219 95 129 13461.2262 9779.39328 27.4% 131 72s
15138 4156 10878.4041 111 132 13461.2262 9847.98410 26.8% 132 75s
18527 3267 cutoff 116 13461.2262 10752.1356 20.1% 134 80s
20390 1876 cutoff 125 13461.2262 11356.6986 15.6% 135 86s
23091 247 infeasible 134 13461.2262 12818.7412 4.77% 129 100s
Cutting planes:
Gomory: 40
Cover: 105
Implied bound: 12
Clique: 1
MIR: 66
StrongCG: 2
Flow cover: 131
Inf proof: 5
Zero half: 2
RLT: 96
Relax-and-lift: 11
Explored 27695 nodes (3021287 simplex iterations) in 101.08 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 13461.2 13495.1 13799.3 ... 14092.7
Optimal solution found (tolerance 1.00e-04)
Best objective 1.346122617578e+04, best bound 1.346122617578e+04, gap 0.0000%
city_info = pd.DataFrame(autonomax.city_info())
city_info
| Index | Name | IsCoreCity | IsControlCenter | Demand | IngoingFlow | OutgoingFlow | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | Boden | False | False | 4.5 | 4.000000e+00 | 8.500000e+00 |
| 1 | 1 | Borås | False | False | 0.7 | 1.030000e+01 | 1.100000e+01 |
| 2 | 2 | Eskilstuna | False | False | 1.1 | 1.563194e-13 | 1.100000e+00 |
| 3 | 3 | Falun | False | False | 2.3 | 0.000000e+00 | 2.300000e+00 |
| 4 | 4 | Gävle | False | False | 1.0 | 4.020000e+01 | 4.120000e+01 |
| 5 | 5 | Göteborg | False | False | 5.8 | 1.350031e-13 | 5.800000e+00 |
| 6 | 6 | Halmstad | False | False | 3.4 | 6.100000e+00 | 9.500000e+00 |
| 7 | 7 | Haparanda | False | False | 4.6 | 0.000000e+00 | 4.600000e+00 |
| 8 | 8 | Helsingborg | False | False | 2.2 | 3.900000e+00 | 6.100000e+00 |
| 9 | 9 | Hudiksvall | False | False | 3.9 | 2.740000e+01 | 3.130000e+01 |
| 10 | 10 | Jönköping | False | False | 1.2 | 1.300000e+01 | 1.420000e+01 |
| 11 | 11 | Kalmar | False | False | 4.0 | 7.247536e-13 | 4.000000e+00 |
| 12 | 12 | Karlskrona | False | False | 1.6 | 2.771117e-13 | 1.600000e+00 |
| 13 | 13 | Karlstad | False | False | 0.9 | 2.844729e-10 | 9.000000e-01 |
| 14 | 14 | Kiruna | False | False | 4.0 | 1.563194e-13 | 4.000000e+00 |
| 15 | 15 | Kristianstad | False | False | 3.0 | 4.654055e-13 | 3.000000e+00 |
| 16 | 16 | Lidköping | False | False | 1.2 | 1.340000e+01 | 1.460000e+01 |
| 17 | 17 | Linköping | False | False | 4.1 | 1.800000e+00 | 5.900000e+00 |
| 18 | 18 | Luleå | False | False | 2.0 | 1.310000e+01 | 1.510000e+01 |
| 19 | 19 | Malmö | False | False | 2.6 | 1.300000e+00 | 3.900000e+00 |
| 20 | 20 | Motala | False | False | 2.4 | 5.900000e+00 | 8.300000e+00 |
| 21 | 21 | Norrköping | False | False | 1.7 | 1.769251e-12 | 1.700000e+00 |
| 22 | 22 | Nyköping | False | False | 4.6 | 8.597567e-13 | 4.600000e+00 |
| 23 | 23 | Sandviken | True | False | 4.5 | 4.350000e+01 | 4.800000e+01 |
| 24 | 24 | Skellefteå | False | False | 4.4 | 1.510000e+01 | 1.950000e+01 |
| 25 | 25 | Skövde | True | False | 2.5 | 3.980000e+01 | 4.230000e+01 |
| 26 | 26 | Stockholm | False | False | 7.0 | 8.455459e-13 | 7.000000e+00 |
| 27 | 27 | Sundsvall | False | False | 0.7 | 2.670000e+01 | 2.740000e+01 |
| 28 | 28 | Trelleborg | False | False | 1.3 | 1.371347e-12 | 1.300000e+00 |
| 29 | 29 | Uddevalla | False | False | 4.0 | 5.800000e+00 | 9.800000e+00 |
| 30 | 30 | Umeå | False | False | 3.2 | 1.950000e+01 | 2.270000e+01 |
| 31 | 31 | Uppsala | False | False | 1.9 | 7.000000e+00 | 8.900000e+00 |
| 32 | 32 | Varberg | False | False | 0.8 | 9.500000e+00 | 1.030000e+01 |
| 33 | 33 | Vetlanda | False | False | 2.1 | 1.090000e+01 | 1.300000e+01 |
| 34 | 34 | Vänersborg | False | False | 3.6 | 9.800000e+00 | 1.340000e+01 |
| 35 | 35 | Västervik | False | False | 1.8 | 2.465583e-12 | 1.800000e+00 |
| 36 | 36 | Västerås | False | False | 1.4 | 1.818989e-12 | 1.400000e+00 |
| 37 | 37 | Växjö | False | False | 2.3 | 4.600000e+00 | 6.900000e+00 |
| 38 | 38 | Örebro | True | True | 4.1 | 1.083000e+02 | 2.202682e-13 |
| 39 | 39 | Örnsköldsvik | False | False | 3.1 | 2.270000e+01 | 2.580000e+01 |
| 40 | 40 | Östersund | False | False | 0.9 | 1.007834e-10 | 9.000000e-01 |
edge_info = pd.DataFrame(autonomax.edge_info())
edge_info
| From | To | Type | Flow | Cost | Distance | |
|---|---|---|---|---|---|---|
| 0 | Skellefteå | Umeå | SUB | 19.5 | 731.139160 | 111 |
| 1 | Skövde | Örebro | CORE | 42.3 | 1320.000000 | 132 |
| 2 | Gävle | Hudiksvall | SUB | -31.3 | 1278.724564 | 118 |
| 3 | Karlskrona | Växjö | SUB | 1.6 | 62.121900 | 102 |
| 4 | Motala | Örebro | SUB | 8.3 | 241.611348 | 92 |
| 5 | Boden | Kiruna | SUB | -4.0 | 637.913000 | 291 |
| 6 | Nyköping | Örebro | SUB | 4.6 | 228.104575 | 131 |
| 7 | Sundsvall | Östersund | SUB | -0.9 | 70.870188 | 166 |
| 8 | Halmstad | Helsingborg | SUB | -6.1 | 145.447337 | 79 |
| 9 | Jönköping | Vetlanda | SUB | -13.0 | 225.433574 | 65 |
| 10 | Umeå | Örnsköldsvik | SUB | 22.7 | 849.479945 | 111 |
| 11 | Boden | Luleå | SUB | 8.5 | 58.656839 | 32 |
| 12 | Lidköping | Skövde | SUB | 14.6 | 168.360541 | 49 |
| 13 | Eskilstuna | Örebro | SUB | 1.1 | 36.303275 | 83 |
| 14 | Karlstad | Örebro | SUB | 0.9 | 29.229970 | 77 |
| 15 | Halmstad | Varberg | SUB | 9.5 | 167.432227 | 65 |
| 16 | Lidköping | Vänersborg | SUB | -13.4 | 206.938975 | 60 |
| 17 | Uddevalla | Vänersborg | SUB | 9.8 | 39.823253 | 21 |
| 18 | Gävle | Sandviken | SUB | 41.2 | 172.857299 | 25 |
| 19 | Linköping | Motala | SUB | 5.9 | 77.952787 | 51 |
| 20 | Linköping | Västervik | SUB | -1.8 | 64.378861 | 97 |
| 21 | Sundsvall | Örnsköldsvik | SUB | -25.8 | 1177.683887 | 127 |
| 22 | Vetlanda | Växjö | SUB | -6.9 | 143.305429 | 72 |
| 23 | Borås | Varberg | SUB | -10.3 | 260.758783 | 84 |
| 24 | Haparanda | Luleå | SUB | 4.6 | 210.858567 | 124 |
| 25 | Luleå | Skellefteå | SUB | 15.1 | 742.410242 | 133 |
| 26 | Stockholm | Uppsala | SUB | 7.0 | 136.873721 | 69 |
| 27 | Kristianstad | Växjö | SUB | 3.0 | 134.707658 | 120 |
| 28 | Falun | Sandviken | SUB | 2.3 | 48.115171 | 65 |
| 29 | Norrköping | Örebro | SUB | 1.7 | 72.868542 | 111 |
| 30 | Gävle | Uppsala | SUB | -8.9 | 140.802752 | 60 |
| 31 | Sandviken | Örebro | CORE | 48.0 | 1790.000000 | 179 |
| 32 | Helsingborg | Malmö | SUB | -3.9 | 67.318060 | 60 |
| 33 | Göteborg | Uddevalla | SUB | 5.8 | 117.417503 | 70 |
| 34 | Malmö | Trelleborg | SUB | -1.3 | 18.150077 | 34 |
| 35 | Jönköping | Skövde | SUB | 14.2 | 337.352659 | 81 |
| 36 | Hudiksvall | Sundsvall | SUB | -27.4 | 641.652314 | 81 |
| 37 | Västerås | Örebro | SUB | 1.4 | 49.705664 | 93 |
| 38 | Borås | Skövde | SUB | 11.0 | 384.262775 | 105 |
| 39 | Kalmar | Vetlanda | SUB | 4.0 | 174.202753 | 119 |
core_cost = sum(edge_info[edge_info['Type'] == 'CORE']['Cost'])
subnet_cost = sum(edge_info[edge_info['Type'] == 'SUB']['Cost'])
total_cost = core_cost + subnet_cost
print(f'core = {core_cost:>9.3f}')
print(f'subnet = {subnet_cost:>9.3f}')
print('------------------')
print(f'total = {total_cost:>9.3f}')
assert abs(autonomax.model.getObjective().getValue() - total_cost) < 1e-6
core = 3110.000 subnet = 10351.226 ------------------ total = 13461.226
visualization.show(pd.DataFrame(autonomax.city_info()), pd.DataFrame(autonomax.edge_info()))